{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #分割等和子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canPartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分割等和子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个非空的正整数数组 <code>nums</code> ，请判断能否将这些数字分成元素和相等的两部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,11,5]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>nums<strong> </strong>可以分割成 [1, 5, 5] 和 [11] 。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,5]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>nums<strong> </strong>不可以分为和相等的两部分\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 416&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/partition-equal-subset-sum/\">https://leetcode-cn.com/problems/partition-equal-subset-sum/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [NUPfPr](https://leetcode.cn/problems/NUPfPr/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [NUPfPr](https://leetcode.cn/problems/NUPfPr/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        smm = sum(nums)\n",
    "        if smm%2==1:\n",
    "            return False\n",
    "        smm //= 2\n",
    "        dp = [0]*(smm+1)\n",
    "        dp[0] = 1\n",
    "        for num in nums:\n",
    "            for i in range(smm, num-1, -1):\n",
    "                dp[i] += dp[i-num]\n",
    "        return dp[-1] > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        target = sum(nums)\n",
    "        if target % 2== 1:return False   \n",
    "        target //= 2\n",
    "        dp = [0]*(target+1)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(target,nums[i]-1,-1):\n",
    "                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])\n",
    "        return dp[target] == target\n",
    "        \n",
    "# target = sum(nums)\n",
    "#         if target % 2 == 1: return False\n",
    "#         target //= 2\n",
    "#         dp = [0] * (target + 1)\n",
    "#         for i in range(len(nums)):\n",
    "#             for j in range(target, nums[i] - 1, -1):\n",
    "#                 dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])\n",
    "#         return target == dp[target]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "\n",
    "        numsSum = sum(nums)\n",
    "\n",
    "        if numsSum < 0 or numsSum & 1 == 1:\n",
    "            return False\n",
    "        \n",
    "        target = numsSum // 2\n",
    "\n",
    "        # \n",
    "        n = len(nums)\n",
    "        dp = [[0]* (target+1) for _ in range(2)]\n",
    "\n",
    "        for i in range(target):\n",
    "            dp[0][i] = nums[0] if nums[0] <= i else 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(target+1):\n",
    "                dp[i&1][j] = max(dp[(i-1)&1][j], (dp[(i-1)&1][j-nums[i]]+nums[i]) if j-nums[i] >= 0 else 0)\n",
    "\n",
    "        return dp[(n-1) & 1][target] == target\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        d = {}\n",
    "        for x in nums:\n",
    "            d2 = {x:1}\n",
    "            for k,v in d.items():\n",
    "                d2[k] = 1;\n",
    "                d2[k+x] = 1;\n",
    "            d = d2;\n",
    "        for k,v in d.items():\n",
    "            if s-k in d and 2*k == s:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        p=set()\n",
    "        p.add(0)\n",
    "        for num in nums:\n",
    "            temp=set()\n",
    "            for i in p:\n",
    "                temp.add(i+num)\n",
    "                temp.add(i-num)\n",
    "            p=temp\n",
    "        return 0 in p\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        p=set()\n",
    "        p.add(0)\n",
    "        for num in nums:\n",
    "            temp=[]\n",
    "            for i in p:\n",
    "                temp.append(i+num)\n",
    "                temp.append(i-num)\n",
    "            p=set(temp)\n",
    "        return 0 in p\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum_nums = sum(nums)\n",
    "        if sum_nums % 2 != 0:\n",
    "            return False\n",
    "        target = sum_nums//2\n",
    "        n = len(nums)\n",
    "        hashmap = {nums[i]:[i] for i in range(n)}\n",
    "        for i in range(target+1):\n",
    "            if i in hashmap.keys():\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                num = nums[j]\n",
    "                if (i - num) in hashmap.keys() and j not in hashmap[i - num]:\n",
    "                    hashmap[i] = hashmap[i - num][:]\n",
    "                    hashmap[i].append(j)\n",
    "                    break\n",
    "        return target in hashmap.keys()\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums) -> bool:\n",
    "        res = []\n",
    "        base = []\n",
    "        total_sum = sum(nums)\n",
    "        mask = [0]*len(nums)\n",
    "        n_len = len(nums)\n",
    "        sum_dict = {}\n",
    "\n",
    "        def backtrack(start_idx, cur_sum):\n",
    "            #print(cur_sum)\n",
    "            #if cur_sum == 18: import pdb;pdb.set_trace()\n",
    "            if cur_sum == total_sum/2: return True\n",
    "            elif cur_sum > total_sum/2: return False\n",
    "            if sum_dict.get(cur_sum, 0) == 1: return False\n",
    "\n",
    "            for i, item in enumerate(nums[start_idx:n_len]):\n",
    "                cur_sum += item\n",
    "                if backtrack(start_idx+i+1, cur_sum): return True\n",
    "                sum_dict[cur_sum] = 1\n",
    "                #sum_dict[total_sum-cur_sum] = 1\n",
    "                cur_sum -= item\n",
    "            return False\n",
    "\n",
    "        return backtrack(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum_nums = sum(nums)\n",
    "        if sum_nums % 2 != 0:\n",
    "            return False\n",
    "        target = sum_nums//2\n",
    "        n = len(nums)\n",
    "        hashmap = {nums[i]:[i] for i in range(n)}\n",
    "        for i in range(target+1):\n",
    "            if i in hashmap.keys():\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                num = nums[j]\n",
    "                if (i - num) in hashmap.keys() and j not in hashmap[i - num]:\n",
    "                    hashmap[i] = hashmap[i - num][:]\n",
    "                    hashmap[i].append(j)\n",
    "                    break\n",
    "        return target in hashmap.keys()\n",
    "                    \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        if s % 2:\n",
    "            return False\n",
    "        target = s // 2\n",
    "        memory = dict()\n",
    "        def traversal(target, startIndex, nums):\n",
    "            if target == 0:\n",
    "                return True\n",
    "            if startIndex in memory and target in memory[startIndex]:\n",
    "                return False\n",
    "            for i in range(startIndex, len(nums)):\n",
    "                if i > startIndex and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                if target - nums[i] >= 0:\n",
    "                    if traversal(target-nums[i], i+1, nums):\n",
    "                        return True\n",
    "            if startIndex not in memory:\n",
    "                memory[startIndex] = []\n",
    "            memory[startIndex].append(target)\n",
    "            return False\n",
    "        return traversal(target, 0, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        _sum = sum(nums)\n",
    "        if _sum % 2 == 1:\n",
    "            return False\n",
    "        target=  int(_sum / 2)\n",
    "\n",
    "        cache = [{} for _ in nums]\n",
    "        def _canPartition(i, target):\n",
    "            if target == 0:\n",
    "                return True\n",
    "            elif target < 0:\n",
    "                return False\n",
    "            else:\n",
    "                if i == len(nums):\n",
    "                    return False\n",
    "                else:\n",
    "                    if target not in cache[i]:\n",
    "                        cache[i][target] = _canPartition(i+1, target-nums[i]) or _canPartition(i+1, target)\n",
    "                    return cache[i][target]\n",
    "        return _canPartition(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        def traverse(start, end, target):\n",
    "            if target in record:\n",
    "                return False\n",
    "            if target == 0:\n",
    "                return True\n",
    "            for i in range(start, end):\n",
    "                result = traverse(i+1, end, target- nums[i])\n",
    "                if result:\n",
    "                    return True\n",
    "                else:\n",
    "                    record.add(target)\n",
    "            return False\n",
    "        \n",
    "        record = set()\n",
    "        sum = 0\n",
    "        for num in nums:\n",
    "            sum += num\n",
    "        if sum % 2:\n",
    "            return False\n",
    "        else:\n",
    "            return traverse(0,len(nums),sum//2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            nonlocal mem\n",
    "            if c == 0:\n",
    "                return True\n",
    "            if c < 0 or mem[c]:\n",
    "                return False\n",
    "            mem[c] = True\n",
    "            return any(dfs(j + 1, c - nums[j]) for j in range(i, len(nums)))\n",
    "        \n",
    "        target, res = divmod(sum(nums), 2)\n",
    "        if res:\n",
    "            return False\n",
    "        mem = [False] * (target + 1)\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        target = sum(nums)\n",
    "        if target % 2 != 0:\n",
    "            return False\n",
    "\n",
    "        self.memo = {}\n",
    "\n",
    "        # 问题转换成 是否存在一个子集等于总和的一半 \n",
    "        return self.dp(nums, 0, target//2)\n",
    "\n",
    "\n",
    "\n",
    "    def dp(self, nums, i, cap):  # 从nums[i:]中选择数字，构建子集，cap表示容量\n",
    "        if \"%s_%s\"%(i,cap) in self.memo.keys():\n",
    "            return self.memo[\"%s_%s\"%(i,cap)]\n",
    "            \n",
    "        if cap == 0:\n",
    "            return True  # 可以完成分割子集\n",
    "\n",
    "        if i == len(nums): # 遍历到最后了，也没有找到，返回False\n",
    "            return False\n",
    "        \n",
    "        # if cap < nums[i]:  # 如果容量小于nums[i],就跳过\n",
    "        #     res = self.dp(nums, i+1,cap)\n",
    "        # elif cap > nums[i]:\n",
    "        #     res = self.dp(nums, i+1,cap-nums[i])\n",
    "\n",
    "        # else:  # cap == nums[i]\n",
    "        #     res = True\n",
    "\n",
    "        # 选中nums[i]\n",
    "        \n",
    "        if cap < nums[i]:  # 如果容量小于nums[i],就跳过\n",
    "            res = self.dp(nums, i+1,cap)\n",
    "        \n",
    "         # 如果容量大于等于nums[i],就可以选择或者不选\n",
    "        else:# cap >= nums[i]:\n",
    "            res = self.dp(nums, i+1,cap-nums[i])\n",
    "            res = res or self.dp(nums, i+1,cap)\n",
    "        \n",
    "        self.memo[\"%s_%s\"%(i,cap)] = res\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n, s = len(nums), sum(nums)\n",
    "        if s % 2:\n",
    "            return False\n",
    "        s = s // 2\n",
    "        dq, visited = deque(), set()\n",
    "        if nums[0] == s:\n",
    "            return True\n",
    "        if nums[0] < s:\n",
    "            dq.append((1, nums[0]))\n",
    "            visited.add((1, nums[0]))\n",
    "        dq.append((1, 0))\n",
    "        visited.add((1, 0))\n",
    "        while dq:\n",
    "            i, cur_s = dq.popleft()\n",
    "            if i == n:\n",
    "                continue\n",
    "            if nums[i] + cur_s == s:\n",
    "                return True\n",
    "            if nums[i] + cur_s < s and (i + 1, nums[i] + cur_s) not in visited:\n",
    "                dq.append((i + 1, nums[i] + cur_s))\n",
    "                visited.add((i + 1, nums[i] + cur_s))\n",
    "            if (i + 1, cur_s) not in visited:\n",
    "                dq.append((i + 1, cur_s))\n",
    "                visited.add((i + 1, cur_s))\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total_sum = sum(nums)\n",
    "        if total_sum % 2 == 1:\n",
    "            return False\n",
    "\n",
    "        tested = {}\n",
    "        def dfs(i, presum):\n",
    "            if presum == total_sum / 2:\n",
    "                return True\n",
    "            \n",
    "            if presum > total_sum / 2:\n",
    "                return False\n",
    "\n",
    "            if i == len(nums):\n",
    "                return False\n",
    "\n",
    "            if (i,presum) in tested:\n",
    "                return tested[(i,presum)]\n",
    "            \n",
    "            if dfs(i+1,presum+nums[i]):\n",
    "                return True\n",
    "            \n",
    "            if dfs(i+1,presum):\n",
    "                return True\n",
    "            \n",
    "            tested[(i,presum)] = False\n",
    "            return False\n",
    "        \n",
    "        return dfs(0,0)\n",
    "                \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total%2 != 0:\n",
    "            return False\n",
    "        else:\n",
    "            target = total/2\n",
    "\n",
    "        record = {}\n",
    "        def dp(i, target):\n",
    "            key = (i,target)\n",
    "            if key in record:\n",
    "                return record[key]\n",
    "            \n",
    "            if target == 0:\n",
    "                return True\n",
    "            if target < 0 or i == len(nums):\n",
    "                return False\n",
    "            \n",
    "            v = dp(i+1, target- nums[i]) or dp(i+1, target)\n",
    "            record[key] = v\n",
    "            return v\n",
    "        \n",
    "        return dp(0, target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums)%2!=0:return False\n",
    "        m = len(nums)\n",
    "        n = sum(nums)//2 +1\n",
    "        dp = [[False]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j==0: dp[i][j] =True\n",
    "                elif j>=nums[i]:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n<2:\n",
    "            return False\n",
    "        \n",
    "        total = sum(nums)\n",
    "        maxNum = max(nums)\n",
    "        if total % 2 == 1:\n",
    "            return False\n",
    "        \n",
    "        target = total//2\n",
    "        if maxNum>target:\n",
    "            return False\n",
    "\n",
    "        dp = [[False] * (target+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = True\n",
    "\n",
    "        dp[0][nums[0]] = True\n",
    "        for i in range(1, n):\n",
    "            num = nums[i]\n",
    "            for j in range(1, target+1):\n",
    "                if j>=num:\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-num]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        \n",
    "        return dp[n-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        # dynamic programming\n",
    "        # 背包问题 dp[i][j] 前i个数字凑成j\n",
    "        total = sum(nums)\n",
    "        if total % 2 == 1:\n",
    "            return False\n",
    "        target = total // 2\n",
    "        if max(nums) > target:\n",
    "            return False\n",
    "        n = len(nums)\n",
    "        dp = [[False] * (target + 1) for _ in range(n + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(target + 1):\n",
    "                # 不选nums[i - 1]\n",
    "                dp[i][j] = dp[i - 1][j]\n",
    "                # 选nums[i - 1]\n",
    "                if j - nums[i - 1] >= 0:\n",
    "                    dp[i][j] = dp[i][j] or dp[i - 1][j - nums[i - 1]] \n",
    "        return dp[-1][-1]\n",
    " \n",
    "\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @functools.cache\n",
    "        def dfs(i, cur_sum):\n",
    "            if cur_sum == target:\n",
    "                return True\n",
    "            if i == len(nums):\n",
    "                return False\n",
    "            \n",
    "            return dfs(i + 1, cur_sum + nums[i]) or dfs(i + 1, cur_sum)\n",
    "        \n",
    "        total = sum(nums)\n",
    "        if total % 2 == 1:\n",
    "            return False\n",
    "        target = total // 2\n",
    "        if max(nums) > target:\n",
    "            return False       \n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        total = sum(nums)\n",
    "        if total % 2 != 0:\n",
    "            return False\n",
    "        target = total // 2\n",
    "        n = len(nums)\n",
    "        dp = [[False] * (target + 1) for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(1, target + 1):\n",
    "                if j == nums[i]:\n",
    "                    dp[i][j] = True\n",
    "                else:\n",
    "                    dp[i][j] = dp[i - 1][j]\n",
    "                    if j > nums[i]:\n",
    "                        dp[i][j] = dp[i][j] or dp[i - 1][j - nums[i]]\n",
    "        return dp[-1][target]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        c = sum(nums)\n",
    "        if(c%2==1):\n",
    "            return False\n",
    "        c = c//2\n",
    "        n = len(nums)\n",
    "        dp = [[False]*(c+1) for _ in range(n+1)]\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,c+1):\n",
    "                if (j>=nums[i-1]):\n",
    "                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        \n",
    "        \n",
    "        return dp[n][c]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        sums = sum(nums)\n",
    "        if( sums % 2 ==1):\n",
    "            return False\n",
    "        target = (int)(sums /2)\n",
    "        dp = [[False for _ in range(target+1)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = True\n",
    "        if (nums[0]<=target):\n",
    "            dp[0][nums[0]] = True\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,target+1):\n",
    "                if(j>=nums[i]):\n",
    "                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]\n",
    "                else :\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        return dp[n-1][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums.sort(reverse=True)\n",
    "        target=sum(nums)\n",
    "        if target%2!=0: return False\n",
    "        target=target//2\n",
    "        n=len(nums)\n",
    "        dp=[[False for j in range(target+1)] for i in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            for j in range(target+1):\n",
    "                if i==0 and j==0:\n",
    "                    dp[i][j]=True\n",
    "                elif i==0 and j!=0:\n",
    "                    dp[i][j]=False\n",
    "                elif i!=0 and j==0:\n",
    "                    dp[i][j]=False\n",
    "                else:\n",
    "                    if dp[i-1][j]:\n",
    "                        dp[i][j]=True\n",
    "                    else:\n",
    "                        if j-nums[i-1]>=0:\n",
    "                            dp[i][j]=dp[i-1][j-nums[i-1]]\n",
    "        return dp[n][target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        target, res = divmod(sum(nums), 2)\n",
    "        if res:\n",
    "            return False\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if c == 0:\n",
    "                return True\n",
    "            return any(dfs(j + 1, c - nums[j]) for j in range(i, len(nums)) if c >= nums[j])\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if c == 0:\n",
    "                return True\n",
    "            if c < 0:\n",
    "                return False\n",
    "            return any(dfs(j + 1, c - nums[j]) for j in range(i, len(nums)))\n",
    "        \n",
    "        target, res = divmod(sum(nums), 2)\n",
    "        if res:\n",
    "            return False\n",
    "        return dfs(0, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums)%2!=0:\n",
    "            return False\n",
    "        target=sum(nums)//2\n",
    "        dp=[[False for i in range(len(nums)+1)] for j in range(target+1)]\n",
    "#dp[i][j]前j个数字能否组合成i\n",
    "        for i in range(1,target+1):\n",
    "            for j in range(1,len(nums)+1):\n",
    "                if nums[j-1]==i:\n",
    "                    dp[i][j]=True\n",
    "                elif nums[j-1]>i:\n",
    "                    dp[i][j]=dp[i][j-1]\n",
    "                else:\n",
    "                    dp[i][j]=dp[i][j-1] or dp[i-nums[j-1]][j-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        # # nums=[1,2,5]\n",
    "        ### dp\n",
    "        val_sum = 0\n",
    "        for val in nums:\n",
    "            val_sum += val\n",
    "        if val_sum%2: return False\n",
    "        else: target_val = val_sum//2\n",
    "        dp = []\n",
    "        for i in range(target_val+1):\n",
    "            dp.append([])\n",
    "            for _ in range(len(nums)+1):\n",
    "                dp[i].append(-1)\n",
    "        # init\n",
    "        for j in range(len(nums)+1):\n",
    "            dp[0][j] = True\n",
    "        for i in range(target_val+1):\n",
    "            dp[i][len(nums)] = False\n",
    "        # dp\n",
    "        for i in range(1, target_val+1):\n",
    "            for j in range(len(nums)-1,-1,-1):\n",
    "                if i-nums[j]>=0:\n",
    "                    dp[i][j] = (dp[i][j+1] or dp[i-nums[j]][j+1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j+1]\n",
    "        return dp[target_val][0]\n",
    "\n",
    "\n",
    "        ### rude recursive\n",
    "        val_sum = 0\n",
    "        for val in nums:\n",
    "            val_sum += val\n",
    "\n",
    "        if val_sum%2: return False\n",
    "        else:\n",
    "            target_val = val_sum//2\n",
    "\n",
    "        def dfs(res, start_i):\n",
    "            if res==0:\n",
    "                return True\n",
    "            elif res<0 or start_i==len(nums):\n",
    "                return False\n",
    "\n",
    "            return dfs(res, start_i+1) or dfs(res-nums[start_i], start_i+1)\n",
    "            \n",
    "        return dfs(target_val, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        import numpy as np\n",
    "        num_sum = sum(nums)\n",
    "\n",
    "        if num_sum % 2 != 0:\n",
    "            return False\n",
    "        \n",
    "        if len(nums) < 2:\n",
    "            return False\n",
    "        \n",
    "        target = num_sum // 2\n",
    "\n",
    "        check_table = np.zeros((target+1, len(nums)), dtype=np.bool)\n",
    "\n",
    "        print(target)\n",
    "        for num_idx, num_now in enumerate(nums):\n",
    "            for target_now in range(0, target+1):\n",
    "                if target_now == num_now:\n",
    "                    check_table[target_now][num_idx] = True\n",
    "                elif target_now < num_now:\n",
    "                    check_table[target_now][num_idx] = check_table[target_now][num_idx-1]\n",
    "                elif target_now > num_now:\n",
    "                    if check_table[target_now][num_idx-1] or \\\n",
    "                        (check_table[target_now-num_now][num_idx-1]) :\n",
    "                        check_table[target_now][num_idx] = True\n",
    "                    else:\n",
    "                        check_table[target_now][num_idx] = False\n",
    "                    \n",
    "                \n",
    "        print(check_table)\n",
    "        if check_table[target][len(nums)-1]:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if len(nums) <= 1 or sum(nums) % 2 == 1:\n",
    "            return False\n",
    "        target = sum(nums) // 2\n",
    "        dp = [[False for i in range(len(nums)+1)] for j in range(target+1)]\n",
    "\n",
    "        for i in range(len(nums)+1):\n",
    "            dp[0][i] = True\n",
    "        for i in range(1, len(nums)+1):\n",
    "            for j in range(1, target+1):\n",
    "                if j >= nums[i-1]:\n",
    "                    dp[j][i] = dp[j-nums[i-1]][i-1] | dp[j][i-1]\n",
    "                else:\n",
    "                    dp[j][i] = dp[j][i-1]\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums_sum=sum(nums)\n",
    "        if nums_sum&1:\n",
    "            return False\n",
    "        target=nums_sum//2  #转换为能否凑出target\n",
    "        nums.sort()\n",
    "        @lru_cache(None)\n",
    "        def f(i,target):\n",
    "            if target==0:\n",
    "                return True\n",
    "            if target<0 or i==len(nums):\n",
    "                return False\n",
    "            return f(i+1,target-nums[i]) or f(i+1,target)\n",
    "        return f(0,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        k=sum(nums)//2\n",
    "        if sum(nums)%2!=0 or nums[-1]>k:\n",
    "            return False\n",
    "        else:\n",
    "            @cache\n",
    "            def bt(path,start):\n",
    "                if start>=len(nums):\n",
    "                    return False\n",
    "                if path==k:\n",
    "                    return True\n",
    "                for i in range(start,len(nums)):\n",
    "                    if path+nums[i]<=k and bt(path+nums[i],i+1):\n",
    "                            return True\n",
    "                return False\n",
    "            return bt(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s = sum(nums)\n",
    "        if s & 1:\n",
    "            return False\n",
    "        ave = s // 2\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        @functools.cache\n",
    "        def dfs(start, tgt):\n",
    "            if tgt == 0:\n",
    "                return True\n",
    "            if start >= n or tgt < 0:\n",
    "                return False\n",
    "            for i in range(start, n):\n",
    "                if tgt - nums[i] < 0:\n",
    "                    break\n",
    "                if dfs(i + 1, tgt - nums[i]):\n",
    "                    return True\n",
    "            return False\n",
    "        return dfs(0, ave)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        @cache\n",
    "        def dfs(target, i):\n",
    "            if target == 0: return True\n",
    "            if target < 0: return False\n",
    "            for j in range(i, len(nums)):\n",
    "                if dfs(target - nums[j], j + 1):\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        nums.sort()\n",
    "        if sum(nums)%2 == 1: return False\n",
    "        target = sum(nums) // 2\n",
    "        return dfs(target, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        s=sum(nums)\n",
    "        n=len(nums)\n",
    "        if s%2==1:\n",
    "            return False\n",
    "        dp=[]\n",
    "        target=s//2\n",
    "        for i in range(n):\n",
    "            dp.append([])\n",
    "            for j in range(target+1):\n",
    "                dp[-1].append(0)\n",
    "        if nums[0]<=target:\n",
    "            dp[0][nums[0]]=1\n",
    "        for i in range(n):\n",
    "            dp[i][0]=1\n",
    "        for i in range(1,n):\n",
    "            for j in range(1,target+1):\n",
    "                if nums[i]<=j:\n",
    "                    dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]\n",
    "                else:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "        return dp[n-1][target]>0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        MAX= sum(nums)\n",
    "        if MAX%2!=0:\n",
    "            return False\n",
    "        self.ans = False\n",
    "        @lru_cache(None)\n",
    "        def dfs(curSum,resIndex):\n",
    "            if curSum == MAX//2:\n",
    "                self.ans = True\n",
    "            if resIndex == len(nums) or self.ans:\n",
    "                return\n",
    "            for nextIndex in range(resIndex+1,len(nums)):\n",
    "                nextVal = nums[nextIndex]\n",
    "                if nextVal+curSum<=MAX//2:\n",
    "                    dfs(nextVal+curSum,nextIndex)\n",
    "        dfs(0,-1)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        tot = sum(nums)\n",
    "        if tot%2!=0:return False\n",
    "        dest = tot//2\n",
    "        self.ans = False\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,cur):\n",
    "            if cur == dest:\n",
    "                self.ans = True\n",
    "                return\n",
    "            if i == len(nums) or cur>dest or self.ans:\n",
    "                return\n",
    "            for j in range(i,len(nums)):\n",
    "                dfs(j+1,nums[j]+cur)\n",
    "        dfs(0,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sumN = sum(nums)\n",
    "        if sumN%2 == 1:\n",
    "            return False\n",
    "        else:\n",
    "            value = sumN//2\n",
    "            # dp ij 表示只有前i个数的话，能否装到j这个值\n",
    "            dp = [[0]*(value+1) for _ in range(len(nums)+1)]\n",
    "            nums.sort()\n",
    "            for i in range(1,len(nums)+1):\n",
    "                for j in range(1,value+1):\n",
    "                    if nums[i-1] == j:\n",
    "                        dp[i][j] = 1\n",
    "                    elif nums[i-1] <j:\n",
    "                        dp[i][j] = dp[i-1][j-nums[i-1]] or dp[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "\n",
    "                if dp[i][-1] == 1:\n",
    "                    return True\n",
    "            print(dp)\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        sum=0\n",
    "        for number in nums:\n",
    "            sum=sum+number\n",
    "        if sum%2!=0:\n",
    "            return False\n",
    "        sum=sum//2\n",
    "        nums.sort()\n",
    "        numlist=numpy.zeros((len(nums)+1,sum+1))\n",
    "        for number in numlist:\n",
    "            number[0]=1\n",
    "        for i in range(0,len(nums)):\n",
    "            for j in range(0,sum+1):\n",
    "                if((j-nums[i]>=0 and numlist[i-1][j-nums[i]]!=0) or numlist[i-1][j]!=0):\n",
    "                    numlist[i][j]=1\n",
    "        print(numlist)\n",
    "        for number in numlist:\n",
    "            if number[sum]==1:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        # 可分解成背包问题\n",
    "        target_sum = sum(nums)\n",
    "        if target_sum % 2 == 1:\n",
    "            return False\n",
    "        target_sum //= 2\n",
    "        # 0-1背包问题\n",
    "        N = len(nums)\n",
    "        dp = [[0]*(target_sum+1) for i in range(N)]\n",
    "        for i in range(1, N):\n",
    "            for j in range(1, target_sum+1):\n",
    "                if j >= nums[i]:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "        # print(dp)\n",
    "        return dp[-1][-1] == target_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums)%2: return False\n",
    "        t=sum(nums)//2\n",
    "        c=[[0]*(t+1) for _ in range(len(nums)+1)]\n",
    "        for i in range(1,len(c)):\n",
    "            for j in range(1,len(c[0])):\n",
    "                if j>=nums[i-1]:\n",
    "                    c[i][j]=max(c[i-1][j],c[i-1][j-nums[i-1]]+nums[i-1])\n",
    "                else: c[i][j]=c[i-1][j]\n",
    "        return c[-1][-1]==t\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        if sum(nums)%2!=0:return False\n",
    "        target=sum(nums)//2\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        dp=[[0]*(target+1) for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(target+1):\n",
    "                if j<nums[i]:\n",
    "                    dp[i][j]=dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])\n",
    "        return dp[n-1][target]==target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        \"\"\"\n",
    "        1. 状态：剩余的背包容量\n",
    "        2. 选择：取或不取\n",
    "        \"\"\"\n",
    "        if sum(nums) % 2 != 0:\n",
    "            return False\n",
    "        weight = sum(nums) // 2\n",
    "        dp = [[0]*(weight+1) for _ in range(len(nums)+1)]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            for j in range(1, weight+1):\n",
    "                if j-nums[i-1] < 0:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "                else:\n",
    "                    dp[i][j] = max(\n",
    "                        dp[i-1][j], # 不选当前的数\n",
    "                        dp[i-1][j-nums[i-1]] + nums[i-1] # 选当前的数 \n",
    "                    )\n",
    "        return dp[len(nums)][weight] == weight\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "\n",
    "        numsSum = sum(nums)\n",
    "\n",
    "        if numsSum < 0 or numsSum & 1 == 1:\n",
    "            return False\n",
    "        \n",
    "        target = numsSum // 2\n",
    "\n",
    "        # \n",
    "        n = len(nums)\n",
    "        dp = [[0]* (target+1) for _ in range(n)]\n",
    "\n",
    "        for i in range(target):\n",
    "            dp[0][i] = nums[0] if nums[0] <= i else 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(target+1):\n",
    "                dp[i][j] = max(dp[i-1][j], (dp[i-1][j-nums[i]]+nums[i]) if j-nums[i] >= 0 else 0)\n",
    "\n",
    "        return dp[n-1][target] == target\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canPartition(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        target = sum(nums) // 2\n",
    "        if target * 2 != sum(nums):\n",
    "            return False\n",
    "\n",
    "        dp = [[0 for _ in range(target+1)] for _ in range(n+1)]\n",
    "        for i in range(1,n+1):\n",
    "            \n",
    "            for j in range(1,target+1):\n",
    "                if j - nums[i-1] >= 0:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1])\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j]\n",
    "\n",
    "            if dp[i][-1] == target:\n",
    "                return True\n",
    "        return False\n",
    "        # dp = [0 for i in range(round(target)+1)]\n",
    "\n",
    "        \n",
    "        # for i in range(0, n):\n",
    "        #     # print(dp)\n",
    "        #     if dp[round(target)] == target:\n",
    "        #         return True\n",
    "        #     for j in range(round(target), -1, -1):\n",
    "        #         # print(j-nums[i])\n",
    "        #         if j-nums[i] >= 0:\n",
    "        #             dp[j] = max(dp[j],dp[j-nums[i]] + nums[i])\n",
    "        \n",
    "        # return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
